155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) – Push element x onto stack.
• pop() – Removes the element on top of the stack.
• top() – Get the top element.
• getMin() – Retrieve the minimum element in the stack.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

Solution:

虽然这是一道简单题，但是并不简单。

1. python

class MinStack:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []

    def push(self, x: int) -> None:
        self.stack.append(x)

    def pop(self) -> None:
        self.stack.pop()

    def top(self) -> int:
        if self.stack:
            return self.stack[-1] 

    def getMin(self) -> int:
        res = self.stack[0]
        for i in range(1, len(self.stack)):
            res = min(res, self.stack[i])
        return res

这是最容易实现和想的一个方法，但是当stack存入太多item的时候，getMin将变得十分耗时，起码是O(n)的时间复杂度。如何解决？我们不如换个思路，当加入item的时候就记录下最小值。这里用到了动态规划的思想，最小值是，前一个数的最小值和当前数做比较来获得的。

class MinStack:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []

    def push(self, x: int) -> None:
        self.stack.append((x, min(x, self.getMin())))
        
    def pop(self) -> None:
        self.stack.pop()

    def top(self) -> int:
        if self.stack:
            return self.stack[-1][0] 

    def getMin(self) -> int:
        if self.stack:
            return self.stack[-1][1]
        return float('inf')

class MinStack:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.minNum = float('inf')

    def push(self, x: int) -> None:
        self.minNum = min(x, self.minNum)
        self.stack.append([x, self.minNum])

    def pop(self) -> None:
        self.stack.pop()[-1]
        # after poping, we need to update minNum
        if self.stack: self.minNum = self.stack[-1][1]
        else: self.minNum = float('inf')

    def top(self) -> int:
        if self.stack:
            return self.stack[-1][0]
        else: return None

    def getMin(self) -> int:
        if self.stack: 
            return self.stack[-1][1]
        else:return None

和上面的异曲同工，但是没有调用内部函数